from collections import deque
import time
from public import *
maze_map=[[]]



def algo_bfs(maze,canvas,start,end,step_x,step_y):
    size_y=len(maze)
    size_x=len(maze[0])
    dis=[[255 for i in range(size_x)]for j in range(size_y)]
    record=[[None for i in range(size_x)]for j in range(size_y)]

    dis[start.y][start.x]=0
    
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    queue=deque()
    queue.append(start)
    while queue:
        find=False
        cur=queue.popleft()#先进先出
        #访问过的标记紫色
        canvas.create_rectangle(cur.x*step_x,cur.y*step_y,(cur.x+1)*step_x,(cur.y+1)*step_y,fill="purple",outline="black")
        canvas.update()
        for i in range(4):
            smell_x,smell_y=cur.x+dx[i],cur.y+dy[i]
            if 0<=smell_x<size_x and 0<=smell_y<size_y and dis[smell_y][smell_x]==255 and maze[smell_y][smell_x]!=1:
                dis[smell_y][smell_x]=dis[cur.y][cur.x]+1
                record[smell_y][smell_x]=cur
                queue.append(pos(smell_x,smell_y))

                canvas.create_rectangle(smell_x*step_x,smell_y*step_y,(smell_x+1)*step_x,(smell_y+1)*step_y,fill="green",outline="black")
                canvas.update()
                time.sleep(0.1)

                if smell_x==end.x and smell_y==end.y:
                    find=True
                    break
        if find==True:
            stack=[]#定义一个栈
            cur=end
            stack.append(cur)
            while cur.x!=start.x or cur.y!=start.y:
                cur=record[cur.y][cur.x]
                stack.append(cur)
            while stack:
                cur=stack.pop()
                canvas.create_rectangle(cur.x*step_x,cur.y*step_y,(cur.x+1)*step_x,(cur.y+1)*step_y,fill="red",outline="black")
                canvas.pack()
            return True
    return False

    
        
